With rapidly increasing amount of data to be stored, there is a need for storage systems to cheaply and promptly remove data that is no longer in use. Traditionally, storage systems have relied on processes such as garbage collectors to identify useful data and to reclaim unused storage space. However, such processes, even if run in the background, consume substantial computing resources. Further, such processes are typically run infrequently, leading to the accumulation of storage space that can otherwise be reclaimed earlier. Finally adding to the cost of data deletion is the often stringent data deletion standards that may be associated with the storage of sensitive data.